﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace DataStuctureStudy.Sorts
{
    /// <summary>
    /// 重复的遍历数组。
    /// 每次遍历都比较两个元素，如果顺序不正确就把他们交换一下。
    /// 如果遍历后只交换了 1 次或 0 次，排序结束。
    /// 最多需要 length -1 次遍历，第 iterTimes 次需要遍历 length - iterTimes - 1 个元素。
    /// </summary>
    class BubbleSort<T>
        where T : IComparable<T>
    {
        private static void Swap(T[] items, int left, int right)
        {
            if (left != right)
            {
                var temp = items[left];
                items[left] = items[right];
                items[right] = temp;
            }
        }

        public static void Sort1(T[] items)
        {
            if (items.Length < 2)
            {
                return;
            }

            int swappedTimes;
            do
            {
                swappedTimes = 0;
                // 重复的遍历数组。
                for (var i = 1; i < items.Length; i++)
                {
                    // 每次遍历都比较两个元素，如果顺序不正确就把他们交换一下。
                    if (items[i - 1].CompareTo(items[i]) > 0)
                    {
                        Swap(items, i - 1, i);
                        swappedTimes++;
                    }
                }
            } while (swappedTimes > 1);// 如果遍历后只交换了 1 次或 0 次，排序结束。
        }

        public static void Sort2(T[] items)
        {
            if (items.Length < 2)
            {
                return;
            }

            int swappedTimes;
            do
            {
                swappedTimes = 0;
                int iterTimes = 0;

                for (var i = 1; i < items.Length - iterTimes; i++)
                {
                    if (items[i - 1].CompareTo(items[i]) > 0)
                    {
                        Swap(items, i - 1, i);
                        swappedTimes++;
                    }
                }
                iterTimes--;
            } while (swappedTimes > 1);
        }

        public static void Sort3(T[] items)
        {
            if (items.Length < 2)
            {
                return;
            }

            for (var i = 1; i < items.Length; i++)
            {
                int swappedTimes = 0;
                for (var j = 1; j < items.Length - i + 1; j++)
                {
                    if (items[j - 1].CompareTo(items[j]) > 0)
                    {
                        Swap(items, j - 1, j);
                        swappedTimes++;
                    }
                }

                if (swappedTimes <= 1)
                {
                    break;
                }
            }
        }

        public static void Sort4(T[] items)
        {
            Sort4Helper(items, 0);
        }

        private static void Sort4Helper(T[] items, int iterTimes)
        {
            if (items.Length < 2)
            {
                return;
            }

            int swappedTimes = 0;
            for (var i = 1; i < items.Length - iterTimes; i++)
            {
                if (items[i - 1].CompareTo(items[i]) > 0)
                {
                    Swap(items, i - 1, i);
                    swappedTimes++;
                }
            }

            if (swappedTimes <= 1)
            {
                return;
            }

            Sort4Helper(items, iterTimes + 1);
        }
    }
}
